package com.ziyucoding.springboot.labs.lab4.algorithm;

import java.util.Arrays;

/**
 * 递归判断结果
 * <p>
 * 题目：
 * 给一个3位长的整型数组，判断这三个数是否通过加减乘3种运算得到数12。
 * [1, 1,1] : false
 * [3,4,5]: true
 * [4,8,5]: true
 * [4,4,4]: true
 *
 * @author ziyucoding
 * @date 2023-04-17
 **/
public class RecursiveJudgmentResult {

    public static void main(String[] args) {
        // 输入的数组
//        int[] nums = {1, 1, 1};
//        int[] nums = {3, 4, 5};
//        int[] nums = {4, 8, 5};
//        int[] nums = {4, 4, 4};
        int[] nums = {1, 2, 4, 5};
        // 期望的结果
        int result = 12;
        boolean flag = canJudgmentToResult(nums, result);
        // 打印内容
        StringBuilder content = new StringBuilder();
        content.append(Arrays.toString(nums));
        content.append(" : ");
        content.append(flag);
        System.out.println(content);
    }

    /**
     * 递归判断整型数组三个数是否通过加减乘3种运算得到结果数
     *
     * @param nums
     * @param result
     * @return boolean
     */
    private static boolean canJudgmentToResult(int[] nums, int result) {
        // 判断参数合法性
//        if (nums.length != 3) {
//            throw new RuntimeException("输入数组不合法");
//        }

        boolean flag = doJudgmentToResult(nums, result);
        return flag;
    }

    /**
     * 递归判断整型数组三个数是否通过加减乘3种运算得到结果数
     *
     * @param nums
     * @param result
     * @return boolean
     */
    private static boolean doJudgmentToResult(int[] nums, int result) {
        if (nums.length == 1) {
            return nums[0] == result;
        } else {
            for (int i = 0; i < nums.length; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    // 加法
                    int[] newNums = getNewNums(nums, i, j, nums[i] + nums[j]);
                    if (doJudgmentToResult(newNums, result)) {
                        return true;
                    }

                    // 减法
                    newNums = getNewNums(nums, i, j, nums[i] - nums[j]);
                    if (doJudgmentToResult(newNums, result)) {
                        return true;
                    }
                    newNums = getNewNums(nums, j, i, nums[j] - nums[i]);
                    if (doJudgmentToResult(newNums, result)) {
                        return true;
                    }

                    // 乘法
                    newNums = getNewNums(nums, i, j, nums[i] * nums[j]);
                    if (doJudgmentToResult(newNums, result)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    /**
     * 获得新数组
     *
     * @param nums
     * @param i
     * @param j
     * @param result
     * @return int
     */
    private static int[] getNewNums(int[] nums, int i, int j, int result) {
        int[] newNums = new int[nums.length - 1];
        int index = 0;
        for (int k = 0; k < nums.length; k++) {
            if (k != i && k != j) {
                newNums[index++] = nums[k];
            }
        }
        newNums[newNums.length - 1] = result;
        return newNums;
    }

}



